//给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。 
//
// 子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。 
//
// 
//
// 示例 1： 
//
// 
//输入：s = "bbbab"
//输出：4
//解释：一个可能的最长回文子序列为 "bbbb" 。
// 
//
// 示例 2： 
//
// 
//输入：s = "cbbd"
//输出：2
//解释：一个可能的最长回文子序列为 "bb" 。
// 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 1000 
// s 仅由小写英文字母组成 
// 
// Related Topics 字符串 动态规划 👍 812 👎 0

package leetcode.editor.cn;
//leetcode submit region begin(Prohibit modification and deletion)
class Solution516 {

    /**
     * 动态规划
     *
     * 这个问题中我们对 memo 数组的定义是： 在子串 s[i…j] 中，要求的最长回文子序列的长度为 memo[i][j]
     * 根本取决于 s[i] 和 s[j] 这两个字符是否相等：
     * （1）若 s[i] = s[j]，那么它俩加上 s[i+1…j-1] 中的最⻓回⽂⼦序列就是 s[i…j] 的最⻓回⽂⼦序列memo[i][j] = memo[i+1][j-1] + 2（注意此处是加上2，而不是1，因为有 s[i] 和 s[j] 这两个字符）;
     * （2）若 s[i] != s[j]，说明他俩不可能同时出现在 s[i…j] 的最长回文子序列中，那么把他们分别加入 s[i+1…j-1] 中，看哪个子串产生的回文子序列更长即可memo[i][j] = max(memo[i+1][j], memo[i][j-1])。
     * ————————————————
     * 版权声明：本文为CSDN博主「oyall520」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
     * 原文链接：https://blog.csdn.net/oyall520/article/details/105471421
     * @param s
     * @return
     */
    public int longestPalindromeSubseq(String s){
        int len = s.length();
        int[][] dp = new int[len][len];
        //初始化只有一个字符的情况，否则递推公式没法推
        for(int i = 0; i < len; i++){
            dp[i][i] = 1;
        }
        for(int i = len-1; i >= 0 ; i--){
            for(int j = i+1; j <len ; j++){
                if(s.charAt(i) == s.charAt(j)){
                    dp[i][j] = dp[i+1][j-1]+2;
                } else {
                    //因为不要求连续，所以当s[i]!=s[j]时，可以只添加s[i]或只添加s[j]
                    //举例：bbbab，s[0][4]=2+s[1][3],但s[1]!=s[3]，此时只添加1或者只添加3，发现最大子序列为2
                    //故结果为4，此时是将a删除了，故不连续
                    //在最长回文字串中，s[i]!=s[j]时，直接就不是回文字串了，因为此时如果删除一个元素就不连续了
                    dp[i][j] =  Math.max(dp[i+1][j],dp[i][j-1]);
                }
            }
        }
        return dp[0][len-1];
    }

    /**
     * 双指针法
     * 错误！！因为回文子串是要连续的，回文子序列可不是连续的！
     * @param s
     * @return
     */
    public int longestPalindromeSubseq1(String s) {
        int len = s.length();
        int result = 0;
        for(int i = 0; i < len; i++){
            result = Math.max(result, extend(s,i,i,len));  //以i为中心点
            result = Math.max(result, extend(s,i,i+1,len)); //以i，i+1为中心点
        }
        return result;
    }

    private int extend(String s, int i, int j, int len) {
        int maxValue = 0;
        while(i >=0 && j <len && s.charAt(i) == s.charAt(j)){
            maxValue = Math.max(maxValue, j-i);
            i--;
            j++;
        }
        return maxValue;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
